package medium

/*
时间复杂度:O(logN)
空间复杂度:O(1)

解题关键:
1.从一个数A,经过一些操作变成B, 一般可以想到DFS(常规解法)
2.如果A的操作类似于: 如果A是偶数,则/2, A是奇数,则xxxx; 那么碰到这种/2的操作,可以将数字化成二进制来看更直观

*/

// A,如果是偶数,则/2, 如果是奇数,则可以+1或-1, 求A->1所需的最少变换次数
// 1.如果二进制表示是0结尾,则最快的就是右移一位
// 2.如果末尾是 01, 则减去末尾的1
// 3.如果末尾是连续的1, 例如: 1111,则最快的办法是+1然后右移位; 但是数字3需要注意,因为11变成1最快的方法是-1然后右移(2次);
// 如果+1然后右移需要3次
func integerReplacement(n int) int {
	ans := 0
	for n != 1 {
		if n%2 == 0 {
			n /= 2
			ans++
		} else if (n&3 == 3) && n != 3 {
			// 这里需要注意, n&3 == 3表示末尾二进制表示是11, 但是如果n+1可能会导致超int32范围,所以直接+1然后右移(相当于(n+1)/2)
			// (n+1)/2的值与n/2+1的值相等
			n = n/2 + 1
			ans += 2
		} else {
			n--
			ans++
		}
	}
	return ans
}
